package sortAlgorithm.mergeSort;

import java.util.Arrays;

/**
 * @author： pang-yun
 * @date： 2021-10-12 20:56
 * 功能目的 ：用于 归并排序
 */

public class MergeDemo {

    public static void main(String[] args) {
        int[] arr= {9,8,7,6,5,4,3};
        int[] assist =new int[arr.length];
        mergesort(arr,0,arr.length-1,assist);
        System.out.println(Arrays.toString(arr));
    }

    public static void mergesort(int[] arr, int low, int high, int[] assist) {
        if (low >= high) return;

        int mid = low + (high - low) / 2;
        mergesort(arr,low,mid,assist);
        mergesort(arr,mid+1,high,assist);

        merge(arr,low,mid,high,assist);
    }
    public static void merge(int[] arr,int low,int mid,int high, int[] assist){
        int arrIndex=low;
        int leftIndex= low;
        int rightIndex= mid+1;

        while (leftIndex<=mid && rightIndex<=high){
            if (arr[leftIndex]<=arr[rightIndex]){
                assist[arrIndex++]=arr[leftIndex++];
            }else {
                assist[arrIndex++]=arr[rightIndex++];
            }
        }

        while (leftIndex<=mid){
            assist[arrIndex++]=arr[leftIndex++];
        }
        while (rightIndex<=high){
            assist[arrIndex++]=arr[rightIndex++];
        }

        for (int i=low;i<=high; i++){
            arr[i]=assist[i];
        }
    }

}
